The term adiabatic quantum computation is generally understood to describe certain methods that employ techniques from quantum physics to solve unconstrained binary optimization problems. The specified optimization problems are generally solved by associating a solution (global minimum) of the optimization problem with a ground state (lowest energy configuration) of a Hamiltonian function.
In practice, the ability of an actual quantum (hardware) device to find such solutions is limited by factors. These factors include, for example, a number of quantum bits or qubits, control precision, and connectivity between qubits. The qubits represent the units of quantum information in the quantum computational structure in much the same way as the standard “bit” does in other computational schemes. A qubit in a general sense represents a two-state quantum-mechanical system, the two states being generally represented as one in the vertical and the other in the horizontal. As such, and unlike a conventional bit, the quantum mechanics allows the qubit to be in a superposition of both states at a same time. It is this property that is fundamental to quantum computing. The logical qubit connectivity required to solve a particular optimization problem can be represented by a graph, which may be referred to as a “problem” graph. The physical qubit connectivity enabled by an actual quantum device can also be represented by a graph, which may be referred to as the “hardware” or “physical” graph. One example of a quantum device that has proven useful for adiabatic quantum computations is the D-WAVE quantum annealing machine, available from D-WAVE Systems, Burnaby, Canada.
There often arise circumstances in which, often due to device limitations, the problem graph cannot be mapped directly onto the hardware graph. Certain techniques exist for overcoming these hardware constraints in solving the optimization problem using a particular quantum device. Such techniques may be referred to as minor embedding techniques. Examples of such minor embedding techniques as examples of known graph embedding techniques are described in U.S. Pat. Nos. 7,984,012 and 8,244,662 to Coury et al.
Other papers describe myriad other known embedding techniques. One such technique is referred to as the TRIAD method. See V. Choi, “Minor-embedding in adiabatic quantum computation: II. Minor-universal graph design,” Quantum Information Processing 10(3), 343-353 (October 2010). The TRIAD method is used to embed arbitrary graphs into a hardware graph built up out of unit cells, each of which is a K(n, n) bipartite graph. It has been found that the TRIAD method is useful for showing that a particularly-indicated hardware graph is useful for any problem graph up to a certain size. This method, as described, is somewhat inefficient and constrains the problem graph to a particular limiting size based on the size of the hardware graph. Klymko et al. developed a method for determining all problem graphs that can be embedded into a hardware graph, but the method lacks scalability and tends to be useful only for small hardware graphs. See C. Klymko, B. D. Sullivan, T. S. Humble, “Adiabatic Quantum Programming: Minor Embedding With Hard Faults,” Quantum Information Processing 13(3):709-729 (March 2014), Klymko et al. also developed a “greedy” algorithm for problem graphs that are complete graphs.
Each of the conventional solutions includes certain shortfalls and constraints that limit the scope, capacity and or efficiency with which a particular problem graph can be mapped to a particular physical (hardware) graph. Optimal minor embedding for an arbitrary problem graph is itself an NP-hard problem.